#include<assert.h>

namespace dt
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;


        const_iterator begin() const
        {
            return _start;
        } 

        const_iterator end() const
        {
            return _finish;
        } 

        iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}
        
        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _end_of_storage = nullptr;
            }
        }

        void reserve(size_t n)
        {
            if (n > _capacity())
            {
                size_t oldsize = size();
                T* tmp = new T[n];

                if (_start)
                {
                    memcpy(tmp, _start, sizeof(T) * size());
                    delete[] _start;
                }

                _start = tmp;
                _finish = _start + oldsize;
                _end_of_storage = _start + n;
            }
        }

        size_t capacity()
        {
            return _end_of_storage - _start;
        } 

        T& operator[](size_t i)
        {
        assert (i < size());

        return _start[i];
        }

        iterator insert(iterator pos, const T& x)  //正常无返回值，这里只是说明pos需要重置
        {
            assert(pos >= _start);
			assert(pos <= _finish);

            if (_finish == _end_of_storage)
            {
                size_t len = pos - _start;

                size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newcapacity);

                pos = _start + len;
                
            }

            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                end--;
            }

            *pos = x;
            _finish++;

            return pos;
        }
        
        void push_back(const T& x)
        {
            insert(end(), x);
        }

        void pop_back()
        {
            assert(size() > 0)
            {
                _finish--;
            }
        }

        void erase(iterator pos)
        {
            assert (pos >= _start);
            assert (pos < _finish);

            iterator it = pos + 1;
            while (it != finish)
            {
                *(it - 1) = *it;
                it++;
            }

            --_finish;
        }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };
}